/*
 * @lc app=leetcode.cn id=67 lang=java
 *
 * [67] 二进制求和
 */

// @lc code=start
class Solution {
    /**
    * Accepted
    294/294 cases passed (1 ms)
    Your runtime beats 99.99 % of java submissions
    Your memory usage beats 53.54 % of java submissions (40.3 MB)
    */
    public String addBinary(String a, String b) {
        String maxS, minS;
        if (a.length() > b.length()) {
            maxS = a;
            minS = b;
        } else {
            maxS = b;
            minS = a;
        }
        int max = maxS.length(), min = minS.length();
        int carry = 0;
        int aVal, bVal;
        StringBuilder result = new StringBuilder();
        for (int i = 1; i <= max; i++) {
            if (i <= min) {
                aVal = minS.charAt(min - i) - '0';
                bVal = maxS.charAt(max - i) - '0';
                carry = carry + aVal + bVal;
            } else {
                bVal = maxS.charAt(max - i) - '0';
                carry += bVal;
            }

            if (carry % 2 == 0) {
                result.append("0");
            } else {
                result.append("1");
            }

            if (carry >= 2) {
                carry = 1;
            } else {
                carry = 0;
            }
        }

        if (carry == 1) {
            result.append("1");
        }

        return result.reverse().toString();
    }
}
// @lc code=end